package leetcode.year2021.month10;

/**
 * 96. 不同的二叉搜索树
 */
public class _23_03NumTrees96 {
  public static void main(String[] args) {
    System.out.println(numTrees(2));
  }
  /**
   * 思路：  动态规划，遍历每个节点，然后将该节点作为根节点，前面的作为左子树，右边的作为右子树
   *
   * 解题思路
   * 标签：动态规划
   * 假设 n 个节点存在二叉排序树的个数是 G (n)，令 f(i) 为以 i 为根的二叉搜索树的个数，则
   * G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)G(n)=f(1)+f(2)+f(3)+f(4)+...+f(n)
   *
   * 当 i 为根节点时，其左子树节点个数为 i-1 个，右子树节点为 n-i，则
   * f(i) = G(i-1)*G(n-i)f(i)=G(i−1)∗G(n−i)
   *
   * 综合两个公式可以得到 卡特兰数 公式
   * G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)G(n)=G(0)∗G(n−1)+G(1)∗(n−2)+...+G(n−1)∗G(0)
   *
   * 作者：guanpengchn
   * 链接：https://leetcode-cn.com/problems/unique-binary-search-trees/solution/hua-jie-suan-fa-96-bu-tong-de-er-cha-sou-suo-shu-b/
   * 来源：力扣（LeetCode）
   * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
   * @param n
   * @return
   */
  public static int numTrees(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i < n + 1; i++) {
      for (int j = 0; j < i; j++) {
        dp[i] += dp[j] * dp[i-j-1];
      }
    }

    return dp[n];
  }

  /**
   * 96. 不同的二叉搜索树
   * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
   *
   * 输入：n = 3
   * 输出：5
   * 示例 2：
   *
   * 输入：n = 1
   * 输出：1
   *
   *
   * 提示：
   *
   * 1 <= n <= 19
   */
}
